/*
Date:20210417 19:17pm
key:经典回溯，不过运行时长有点拉跨，没办法了哦。
*/
class Solution {
public:
    void back(vector<int>& candidates,set<vector<int>>& s,vector<int>& v,int&count,int&target)
    {
        if(count>=target)
        {
            if(count==target)
            {
                vector<int>v1=v;
                sort(v1.begin(),v1.end());
                s.insert(v1);
                
            }
            
            return;
        }
        else
        {
            for(int j:candidates)
            {
                //有一个元素时判断模是不是等于0及早地制止无效递归。
                if(v.size()==1&&v[0]==j)
                {
                    if(target%j!=0){continue;}
                }
                v.push_back(j);
                count+=j;
                back(candidates, s, v, count,target);
                count-=j;
                v.pop_back();
            }
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) 
    {
        vector<vector<int>> V;
        vector<int> v;
        set<vector<int>> s;
        int count=0;
        //cout<< accumulate(candidates.begin(),candidates.end(),0);
        back(candidates,s,v,count,target);
        for(auto j:s)
        {
            V.push_back(j);
        }
        return V;
    }
};